// https://leetcode.cn/problems/isomorphic-strings/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 双哈希表映射，s2t记录s->t映射，t2s记录t->s映射
// 2. 遍历字符串，检查当前字符映射是否一致
// 3. 发现冲突立即返回false，无冲突则建立映射
// 4. 时间复杂度：O(n)，空间复杂度：O(字符集大小)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>

class Solution 
{
public:
    bool isIsomorphic(string s, string t) 
    {
        int len = s.size();

        unordered_map<char, char> s2t;
        unordered_map<char, char> t2s;
        
        for (int i = 0 ; i < len ; i++)
        {
            char a = s[i], b = t[i];

            if (s2t.find(a) != s2t.end() && s2t[a] != b)
            {
                return false;
            }
            if (t2s.find(b) != t2s.end() && t2s[b] != a)
            {
                return false;
            }

            s2t[a] = b;
            t2s[b] = a;
        }

        return true;
    }
};

int main()
{
    string s1 = "egg", t1 = "add";
    string s2 = "foo", t2 = "bar";
    string s3 = "paper", t3 = "title";

    Solution sol;

    cout << (sol.isIsomorphic(s1, t1) == 1 ? "True" : "False") << endl;
    cout << (sol.isIsomorphic(s2, t2) == 1 ? "True" : "False") << endl;
    cout << (sol.isIsomorphic(s3, t3) == 1 ? "True" : "False") << endl;

    return 0;
}